The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Border Gateway Protocol (BGP) is a path vector routing protocol for exchanging routing information among network elements in the same or different Autonomous System (AS). The function of a BGP-enabled network element (a BGP host or peer) is to exchange network reachability information with other BGP-enabled network elements. The most commonly implemented version of BGP is BGP-4, which is defined in RFC1771 (published by the Internet Engineering Task Force (IETF) in March 1995).
To exchange routing information, two BGP hosts first establish a BGP peering session by exchanging BGP OPEN messages. The BGP hosts then exchange their full routing tables. After this initial exchange, each BGP host sends to its BGP peer or peers only incremental updates for new, modified, and unavailable or withdrawn routes in one or more BGP UPDATE messages. A route is a unit of information that pairs a network destination with the attributes of a network path to that destination. Examples of path attributes include, but are not limited to, the ORIGIN attribute (which indicates how a BGP peer learned about a route), the AS_PATH attribute (which indicates the Autonomous Systems through which a route passes), the NEXT_HOP attribute (which is the address of the border router that is the next hop in a route), and the LOCAL_PREF attribute (which indicates the BGP peer's degree of preference of an exit point from the local AS for a route).
As defined in RFC1771, BGP-4 accommodates the exchange of only Internet Protocol version 4 (IPv4) unicast routes. The Multiprotocol Extension for BGP (MP-BGP) defined in RFC2858 (published by IETF in June 2000) accommodates the exchange of routing information for multiple Network Layer protocols, such as, for example, Internet Protocol version 6 (IPv6), Internetwork Packet eXchange (IPX), Appletalk, Banyan Vines, Asynchronous Transfer Mode (ATM), X.25, and Frame Relay.
In order to enable the exchange of multi-protocol reachability information, MP-BGP introduced two new path attributes that may be used in a BGP UPDATE message, MP_REACH_NLRI and MP_UNREACH_NLRI. The MP_REACH_NLRI path attribute provides for advertising feasible (or reachable) routes to a BGP peer, where the feasible routes are included in a Network Layer Reachability Information (NLRI) field as <length, prefix> tuples. The MP_UNREACH_NLRI path attribute provides for withdrawing multiple unfeasible (or unreachable) routes from service, where the unfeasible routes are included in a Withdrawn Routes field as <length, prefix> tuples.
FMP-BGP also introduced two single-value parameters which are included in both the MP_REACH_NLRI and MP_UNREACH_NLRI path attributes of a BGP UPDATE message: the Address Family Identifier (AFI) and the Subsequence Address Family Identifier (SAFI). The AFI parameter carries the identity of the network layer protocol associated with the network address that follows next in the path to the destination. The SAFI parameter provides additional information about the type of the Network Layer Reachability Information that is included in a BGP UPDATE message, and the values defined for this parameter usually indicate a type of communication forwarding mechanism, such as, for example, unicast or multicast. The AFI/SAFI combination is commonly used to identify a family of addresses. For example, an AFI/SAFI combination of “1/1” identifies IPv4 unicast addresses and an AFI/SAFI combination of “2/2” identifies IPv6 multicast addresses. In the context of BGP, the AFI/SAFI combination associated with a route usually indicates a type of the route's prefixes, the format the route's prefixes, and how to interpret the routes included in BGP UPDATE messages.
As networks grow more complex and the number of BGP hosts in Autonomous Systems increases, managing BGP sessions between BGP hosts in the same or different Autonomous Systems becomes more difficult. In a typical Autonomous System, it is desirable for each BGP host to exchange routing information with each other BGP host in the system in order to facilitate efficient routing of local and transit network traffic. However, to enable two BGP hosts to establish a BGP session, a user (such as a network engineer) must manually configure both BGP hosts so that the hosts can identify one another and establish a BGP peerin session. In an Internet Service Provider (ISP) autonomous system that has hundreds, sometimes even thousands of BGP hosts, it is a daunting task for a network engineer to fully mesh the BGP hosts by manually configuring BGP sessions among them.
An approach that reduces the need for manual configuration in the creation of a full BGP mesh among the internal BGP hosts of an Autonomous System is provided in a co-pending patent application Ser. No. 10/791,630, filed Mar. 1, 2004, entitled “TECHNIQUES FOR AUTOMATICALLY CREATING AN IBGP MESH,” of Robert Raszuk, and assigned to the same assignee hereof. The approach described in Raszuk is suitable for exchanging IPv4 unicast routes in an Autonomous System in which a large number of internal BGP hosts need to participate in an internal BGP (iBGP) mesh, but does not fully address all issues described in this disclosure. For example, the approach described in Raszuk uses an Internal Gateway Protocol (IGP) for flooding auto-discovery information to the internal BGP hosts. The approach described herein is more suitable to be used in a network in which the BGP hosts are established on the edges of the network and in which there is not need to have any BGP state information flooded by IGP among internal BGP hosts.
Further, the approach described in Raszuk does not provide for automatically discovering BGP peers that are established on the edges of the Autonomous System and that exchange routes having a variety of route types that are maintained only by edge network elements. Examples of routes maintained only by edge network elements include, but are not limited to, Virtual Private Network (VPN) routes (as described in RFC2547, published by IETF in March 1999), Layer 3 VPN (L3VPN) routes, Layer 2 VPN (L2VPN) routes, and Multi-Protocol Label Switching (MPLS)/IP tunnel core routes.
Further, in the approach described in Raszuk, the static information used for establishing a full iBGP mesh is flooded to the internal BGP hosts over an Open Shortest Path First (OSPF) protocol, which is an Internal Gateway Protocol (IGP) that is not used to facilitate inter-AS routing information exchange. Thus, the approach in Raszuk does not address the issue of providing automatic discovery of BGP peers within External Gateway Protocols (EGP), such as, for example, BGP-4 or MP-BGP compliant protocols.